/**
 * https://leetcode-cn.com/problems/first-missing-positive/
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 * @param nums 
 */
const firstMissingPositive = (nums: number[]): number => {
    // 思路就是把数组排序成, [1, nums.length] 的值, 然后从前往后遍历, 找到第一个不匹配的值, 后返回
    const len = nums.length;
    // [-1, 4, 3, 1]
    for (let i = 0; i < len; i++) {
        // 当前的值在[1, len] 的范围内并是该元素理想所在的位置的值和当前值不一样时, 防止死循环
        // nums[i] - 1 是该元素理想所在的位置
        while(nums[i] >= 1 && nums[i] <= len && nums[nums[i] - 1] !== nums[i]) {
            // console.log(nums[i], nums[nums[i] - 1])
            // 交换位置, 并且对交换后的该位置的元素继续交换
            const tmp = nums[nums[i] - 1]
            nums[nums[i] - 1] = nums[i];
            nums[i] = tmp

            //! 顺序不能反了X
            // const tmp = nums[i]
            // nums[i] = nums[nums[i] - 1];
            // nums[nums[i] - 1] = tmp
            
        }
    }


    for (let i = 0; i < len; i++) {
        // 找到不符合顺序的, 直接返回
        if (nums[i] !== i + 1) return i + 1
    }   

    // 都是已经排好序的了[1, 2, 3, 4]
    return len + 1
};


console.log(firstMissingPositive([3, 4, -1, 1]))